﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace KnightShortestPath
{
    /// <summary>
    /// This class models the tree of possible movements the knight has to move 
    /// from the initial position to the finale position.
    /// </summary>
    public class Tree
    {
        /// <summary>
        /// Instance of the <see cref="KnightShortestPath.Node"/> class that represents the 
        /// root of the tree
        /// </summary>
        private Node root;

        /// <summary>
        /// Creates a new instance of the <see cref="KnightShortestPath.Tree"/> class.
        /// </summary>
        /// <param name="root">
        /// Root: root of the tree.
        /// </param>
        public Tree(Node root) {
            this.root = root;            
        }

        /// <summary>
        /// Creates a new instance of the <see cref="KnightShortestPath.Tree"/> class.
        /// </summary>
        public Tree() : this(new Node()) { }

        /// <summary>
        /// Root Property: Gets the value of root.
        /// </summary>
        public Node Root
        {
            get { return root; }
        }
        
        /// <summary>
        /// Adds an instance of the <see cref="KnightShortestPath.Node"/> class to the tree on a specific places
        /// </summary>
        /// <param name="currentNode">
        /// CurrentNode: Instance of the <see cref="KnightShortestPath.Node"/> class where the new node will be added
        /// </param>
        /// <param name="index">
        /// Index: Index of the child of the instance of <see cref="KnightShortestPath.Node"/> where the new node will 
        /// be added
        /// </param>
        /// <param n-ame="newNode">
        /// New Node: Instance of <see cref="KnightShortestPath.Node"/> that will be added to the tree
        /// </param>
        public void AddNode(Node currentNode, int index, Node newNode) 
        {
            Node toAdd = FindFirstNode(currentNode);
            toAdd.Child[index] = newNode;
            newNode.Parent = toAdd;
        }

        /// <summary>
        /// Finds on the tree a wanted node
        /// </summary>
        /// <param name="wanted">
        /// Wanted: Instance of the <see cref="KnightShortestPath.Node"/> class that represents a wanted position 
        /// on a chessboard
        /// </param>
        /// <returns>
        /// Returns the first instance of <see cref="KnightShortestPath.Node"/> equals to the wanted node.
        /// </returns>
        public Node FindFirstNode(Node wanted) {
            return Seek(this.root, wanted);
        }

        /// <summary>
        /// Seeks on a instance of the <see cref="KnightShortestPath.Node"/> class and in its children for a wanted node
        /// </summary>
        /// <param name="current">
        /// Current: Instance of <see cref="KnightShortestPath.Node"/> or root of the tree where the wanted node will be seeked
        /// </param>
        /// <param name="wanted">
        /// Wanted: Instance of <see cref="KnightShortestPath.Node"/> that will be seek on a tree
        /// </param>
        /// <returns>
        /// Returns a instance of <see cref="KnightShortestPath.Node"/> that represents the found object, otherwise, null.
        /// </returns>
        private Node Seek(Node current, Node wanted) 
        {
            if (current != null){
                if (current.Equivalent(wanted)){
                    return current;
                }
                else {
                    // seeks for the wanted node in each child
                    foreach (Node n in current.Child){
                        Node found = Seek(n, wanted);
                        if(found != null){
                            return found;
                        }
                    }
                }
            }
            return null;
        }

        /// <summary>
        /// Finds on the tree all instances of the <see cref="KnightShortestPath.Node"/> class 
        /// <see cref="KnightShortestPath.Node.Equivalent"/> to the wanted node
        /// </summary>
        /// <param name="wanted">
        /// Wanted: Instance of <see cref="KnightShortestPath.Node"/> that will be seek on a tree
        /// </param>
        /// <returns>
        /// Returns a list of instances equivalents to the wanted node
        /// </returns>
        public List<Node> FindAllNodes(Node wanted)
        {
            return this.FindAllNodes(this.root, wanted, new List<Node>());
        }

        /// <summary>
        /// Find on the tree all instances of the <see cref="KnightShortestPath.Node"/> class 
        /// <see cref="KnightShortestPath.Node.Equivalent"/> to the wanted node
        /// </summary>
        /// <param name="currentNode">
        /// Current Node: Instance of <see cref="KnightShortestPath.Node"/> or root of the tree where the wanted node will be seeked
        /// </param>
        /// <param name="wantedNode">
        /// Wanted Node: Instance of <see cref="KnightShortestPath.Node"/> that will be seek on a tree
        /// </param>
        /// <param name="nodesFound">
        /// Nodes Found: List of instances of the <see cref="KnightShortestPath.Node"/> class that contains each node in the tree equivalent 
        /// to the wanted node.
        /// </param>
        /// <returns>
        /// Returns a list of instances equivalents to the wanted node or null if there is none node on the equivalent to the wanted node
        /// </returns>
        private List<Node> FindAllNodes(Node currentNode, Node wantedNode, List<Node> nodesFound)
        {
            if (currentNode != null)
            {
                if (currentNode.Equivalent(wantedNode))
                {
                    nodesFound.Add(currentNode);
                }
                for (int i = 0; i < 8; i++)
                {
                    if (currentNode.Child[i] != null)
                    {
                        nodesFound = this.FindAllNodes(currentNode.Child[i], wantedNode, nodesFound);
                    }
                }
            }
            return nodesFound;
        }

        /// <summary>
        /// Validates if a instance of <see cref="KnightShortestPath.Node"/> represents an ancestor to
        /// another instance of <see cref="KnightShortestPath.Node"/>
        /// </summary>
        /// <param name="currentNode">
        /// Current Node: instance of <see cref="KnightShortestPath.Node"/> that may have ancestors
        /// </param>
        /// <param name="ancestorNode">
        /// Ancestor Node: instance of <see cref="KnightShortestPath.Node"/> that represents an ancestors
        /// </param>
        /// <returns>
        /// True if the ancestor node is an ancestor of the current node, otherwise, False
        /// </returns>
        public bool IsAncestor(Node currentNode, Node ancestorNode)
        {
            if (currentNode != null) {
                if (currentNode.Equivalent(ancestorNode))
                {
                    return true;
                }
                else {
                    return IsAncestor(currentNode.Parent, ancestorNode);
                }
            }
            return false;
        }

        /// <summary>
        /// Clones a tree starting by an specific node
        /// </summary>
        /// <param name="toClone">
        /// To Clone: Instance of the <see cref="KnightShortestPath.Node"/> class that will be used as a starting 
        /// point to clone a tree or a branch of a tree
        /// </param>
        /// <returns>
        /// Returns the instance of <see cref="KnightShortestPath.Node"/> which contains the root of the cloned tree
        /// </returns>
        public Node CloneTree(Node toClone)
        {
            Node father = this.FindFirstNode(toClone);
            return new Node(father);

        }

        /// <summary>
        /// Calculates the number of level of a tree 
        /// </summary>
        /// <param name="node">
        /// Node: instance of <see cref="KnightShortestPath.Node"/> that will be used as a root to find the number of levels
        /// </param>
        /// <returns>
        /// Returns the number of levels of a specific tree
        /// </returns>
        public int LevelsNumber(Node node)
        {
            if(node == null){
                return 0;
            }
            else{
                return 1 + this.LevelsNumber(node.Parent);
            }
        }        

        /// <summary>
        /// Obtains the ancestor's line of an specific instance of <see cref="KnightShortestPath.Node"/>
        /// The ancestor's line represents the sequence movements that the knight has moved to be on its 
        /// current position
        /// </summary>
        /// <param name="pathEnd">
        /// Path End: last node in the ancestor's line
        /// </param>
        /// <returns>
        /// Returns a lis of instances of <see cref="KnightShortestPath.Node"/> representing the ancestor's line
        /// </returns>
        public List<Node> FindAncestorsLine(Node pathEnd)
        {
            List<Node> ancestorsLine = new List<Node>();
            return this.FindAncestorsLine(pathEnd,ancestorsLine);
        }


        /// <summary>
        /// Obtains the ancestor's line of an specific instance of <see cref="KnightShortestPath.Node"/>
        /// The ancestor's line represents the sequence movements that the knight has moved to be on its 
        /// current position
        /// </summary>
        /// <param name="node">
        /// Node: last node in the ancestor's line
        /// </param>
        /// <param name="ancestorsLine">
        /// Ancestor's Line: List of instances of <see cref="KnightShortestPath.Node"/> representing the 
        /// ancestor's line
        /// </param>
        /// <returns>
        /// Returns a lis of instances of <see cref="KnightShortestPath.Node"/> representing the ancestor's line
        /// </returns>
        private List<Node> FindAncestorsLine(Node node, List<Node> ancestorsLine)
        {
            if(node == null){
                return ancestorsLine;
            }
            else{
                ancestorsLine.Add(node);
                return this.FindAncestorsLine(node.Parent, ancestorsLine);
            }
        }

        /// <summary>
        /// Calculates the number of nodes in a tree.
        /// The number of nodes represents the number of possible movements calculated
        /// </summary>
        /// <param name="node">
        /// Node: Instance of <see cref="KnightShortestPath.Node"/> representing the root of a tree
        /// </param>
        /// <returns>
        /// Returns the number of nodes in a tree
        /// </returns>
        public long NodesNumber() {
            return this.NodesNumber(this.root);
        }

        /// <summary>
        /// Calculates the number of nodes in a tree.
        /// The number of nodes represents the number of possible movements calculated
        /// </summary>
        /// <param name="node">
        /// Node: Instance of <see cref="KnightShortestPath.Node"/> representing the root of a tree
        /// </param>
        /// <returns>
        /// Returns the number of nodes in a tree
        /// </returns>
        public long NodesNumber(Node node) {
            if (node == null)
            {
                return 0;
            }
            else {
                long sum = 0;
                foreach(Node n in node.Child){
                    sum += NodesNumber(n);
                }
                return 1 + sum;
            }
        }
    }
}
